# coding=utf-8
# Date: 2021/9/12 10:51


# 执行用时：36 ms, 在所有 Python3 提交中击败了64.32%的用户
# 内存消耗：14.9 MB, 在所有 Python3 提交中击败了78.92%的用户
class Solution:
    def __init__(self):
        self.N = 35
        self.f = [[0, 0] for _ in range(self.N)]

    def findIntegers(self, n: int) -> int:

        self.init()

        nums = []
        while n != 0:
            nums.append(n % 2)
            n //= 2

        res = 0
        last = 0
        for i in range(len(nums) - 1, -1, -1):
            x = nums[i]

            if x != 0:
                res += self.f[i + 1][0]
                if last == 1:
                    break
            last = x

            if i == 0:
                res += 1
        return res

    def init(self):
        self.f[1][0] = self.f[1][1] = 1
        for i in range(2, self.N):
            self.f[i][0] += self.f[i - 1][0] + self.f[i - 1][1]
            self.f[i][1] += self.f[i - 1][0]


if __name__ == "__main__":
    print(Solution().findIntegers(5))  # 5
    print(Solution().findIntegers(100))  # 34
